package com.leetcode.algorithm.y22.m07;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 394. 字符串解码
 * 
 * https://leetcode.cn/problems/decode-string/
 * 
 * @author jie.deng
 *
 */
class Question0394Solution01 {
	
	public String decodeString(String s) {
		Deque<String> stack = new ArrayDeque<>();
		int len = s.length();
		int idx = 0;
		while (idx < len) {
			if (s.charAt(idx) >= '0' && s.charAt(idx) <= '9') {
				int num = 0;
				while (idx < len && (s.charAt(idx) >= '0' && s.charAt(idx) <= '9')) {
					num *= 10;
					num += (s.charAt(idx) - '0');
					idx++;
				}
				stack.push("" + num);
			} else if (s.charAt(idx) >= 'a' && s.charAt(idx) <= 'z') {
				StringBuilder builder = new StringBuilder();
				while (idx < len && (s.charAt(idx) >= 'a' && s.charAt(idx) <= 'z')) {
					builder.append(s.charAt(idx));
					idx++;
				}
				stack.push(builder.toString());
			} else if (s.charAt(idx) == '[') {
				stack.push("[");
				idx++;
			} else if (s.charAt(idx) == ']') {
				StringBuilder builder = new StringBuilder();
				while (stack.peek() != "[") {
					builder.insert(0, stack.pop());
				}
				stack.pop(); // "["
				int num = Integer.parseInt(stack.pop());
				String str = builder.toString();
				while (num > 1) {
					builder.append(str);
					num--;
				}
				stack.push(builder.toString());
				idx++;
			}
		}
		StringBuilder retBuilder = new StringBuilder();
		while (!stack.isEmpty()) {
			retBuilder.insert(0, stack.pop());
		}
		return retBuilder.toString();
	}
    
}